package algorithm.t202111;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/17 9:27
 * @description :11道
 * 珍惜时间。
 * persevere to last
 * 2021.11.17
 * 2021年11月17日21:28:00
 * 李红磊
 */
public class t20211117 {

    //318.最大单词长度乘积
    public int maxProduct(String[] words) {
        if (words == null) return 0;
        int len = words.length, res = 0;

        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                int flag = 0;
                String temp = words[j];
                for (int k = 0; k < temp.length(); k++) {
                    if (words[i].indexOf(temp.charAt(k)) != -1) {
                        flag++;
                        break;
                    }
                }
                if (flag != 0) continue;
                res = Math.max(res, words[i].length() * temp.length());

            }
        }

        return res;
    }

    public int maxProduct2(String[] words) {
        if (words == null) return 0;
        int len = words.length;
        int[] arr = new int[len];//存放字母的二进制表示
        int res = 0;

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                arr[i] |= 1 << (words[i].charAt(j) - 'a');
            }

        }

        //将不含共同字母的单词相乘，得到最大值
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if ((arr[i] & arr[j]) == 0) {
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }

    //剑指26.树的子结构
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null || A == null) return false;
        return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean dfs(TreeNode rootA, TreeNode rootB) {
        if (rootA == null && rootB == null) return true;
        if (rootA == null) return false;
        if (rootB == null) return true;
        if (rootA.val != rootB.val) return false;

        return dfs(rootA.left, rootB.left) && dfs(rootA.right, rootB.right);
    }

    //剑指27.二叉树的镜像
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return root;
        ArrayDeque queue = new ArrayDeque<TreeNode>() {{
            addLast(root);
        }};
        while (!queue.isEmpty()) {
            TreeNode poll = (TreeNode) queue.pollLast();
            if (poll.left != null) queue.addLast(poll.left);
            if (poll.right != null) queue.addLast(poll.right);
            TreeNode tem = poll.left;
            poll.left = poll.right;
            poll.right = tem;

        }
        return root;
    }

    //剑指28.对称的二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return false;
        ArrayDeque queue = new ArrayDeque<TreeNode>() {{
            addLast(root);
        }};
        while (!queue.isEmpty()) {
            TreeNode k = (TreeNode) queue.poll();
            if (k.left != null) queue.addLast(k.left);
            if (k.right != null) queue.addLast(k.right);

            int size = queue.size();
            for (int i = 0; i < size; i++) {


            }


        }


        return false;
    }

    //剑指10。斐波那契数列1
    public int fib(int n) {
        return 0;
    }

    //剑指10.青蛙跳台阶
    public int numWays(int n) {
        return 0;
    }

    //剑指63.股票的最大利润
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) return 0;
        int len = prices.length;
        int[] dp = new int[len + 1];
        int min = prices[0];

        for (int i = 2; i <= len; i++) {
            min = Math.min(min, prices[i - 1]);
            dp[i] = Math.max(prices[i - 1] - min, dp[i - 1]);
        }
        return dp[len];
    }

    //剑指42.连续子数组的最大和
    public int maxSubArray(int[] nums) {
        return 0;
    }

    //剑指47。礼物的最大价值
    public int maxValue(int[][] grid) {
        if (grid == null) return 0;
        int rows = grid.length, columns = grid[0].length;
/*
    以grid作为dp数组
    grid[i][j]：表示以（i，j）为目标点所能获得最大礼物的价值
     例如 以(0,0)为目标点，获得的最大价值就是gird[0][0](出生就在罗马)
    再例如：以（0,1）为目标点，因为i为0，所以我们可以知道到达目标点的唯一方法就是从左边过来的，最大价值为gird[0][0]+grid[0][1]

 */

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0) {
                    grid[i][j] = grid[i][j] + grid[i][j - 1];
                } else if (j == 0) {
                    grid[i][j] = grid[i][j] + grid[i - 1][j];
                } else {
                    grid[i][j] = Math.max(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];
                }
            }
        }
        return grid[rows - 1][columns - 1];
    }

    //剑指46.把数字翻译成字符串
    public int translateNum(int num) {
        if (num < 10) return 1;
    /*
        dp[i]：表示以xi结尾的数字可以被翻译成字母的个数
        如x=12258
        dp[0]:表示以第0个数字结尾可以被翻译成字母的个数，真实为0，这里我们给1
        dp[1]:表示以第1个数字结尾可以被翻译成字母的个数，就是1可以被翻译成字母的个数
        到了dp[2]以后，就开始判断了
        比如
        dp[2]；以第2个数字结尾的数字，即12，12∈10~25，可以被构成数字，则dp[2]=dp[2-1]+dp[2-2]=2（一个是1 2，一个是12）
        另一个案例
        x=36521
        dp[2]:以第2个数字结尾的数字，即36,36!∈10~25，不能被构成数字，则dp=dp[2-1]=1（只有3 6）
     */
        String str = String.valueOf(num);

        int[] dp = new int[str.length() + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= str.length(); i++) {
            char t1 = str.charAt(i - 2);
            char t2 = str.charAt(i - 1);
            Integer k = Integer.valueOf(t1 + "" + t2);
            if (k >= 10 && k <= 25) dp[i] = dp[i - 1] + dp[i - 2];
            else {
                dp[i] = dp[i - 1];
            }

        }

        return dp[str.length()];
    }

    //剑指48.最长不含重复字符的子字符串
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 1) return 1;
        int res = 1, len = s.length();
        int slow = 0, fast = 1;

        for (; slow < len && fast < len; ) {
            if (s.charAt(slow) != s.charAt(fast)) {

                while (slow < len && fast < len && s.charAt(slow) != s.charAt(fast)) {
                    fast++;
                }
                res = Math.max(res, fast - slow);
                slow = fast;
                fast += 1;
            } else {
                slow++;
                fast++;
            }

        }


        return res;
    }

    public int lengthOfLongestSubstring2(String s) {
        HashMap<Character, Integer> map = new HashMap<>();

        int res = 0, tem = 0;

        for (int i = 0; i < s.length(); i++) {
            int k = map.getOrDefault(s.charAt(i), -1);
            map.put(s.charAt(i), i);//更新字符出现的位置
            tem = tem < (i - k) ? tem + 1 : i - k;
            res = Math.max(res, tem);
        }
        return res;
    }

    public static void main(String[] args) {
        t20211117 t20211117 = new t20211117();
        //System.out.println(t20211117.maxProduct(new String[]{"abcw","baz","foo","bar","xtfn","abcdef"}));
        String s1 = "abcd";
        String s2 = "q";
        int test = 0;

        System.out.println(t20211117.lengthOfLongestSubstring2("pwwkew"));


    }

}
